FIG. 1 is a block diagram of a prior-art system 100 for allocating bandwidth for, scheduling, and transmission of data packets within a packet switched communication system. Data packets associated with various flows arrive randomly and are kept in queues until they are transmitted or discarded. System 100 determines (along with other components), the Quality of Service (QoS) received by each flow, wherein QoS is based on a plurality of performance parameters including bandwidth, delay, and jitter. The QoS received by a flow is subject to constraints specified in a predetermined service level agreement, wherein the service level agreement is a contract that governs the behavior of a provider and a user of a service, namely data transmission. System 100 comprises bandwidth manager 101, packet scheduler 103, and packet handler 105.
Bandwidth manager 101 reserves an appropriate amount of bandwidth for each data flow when it is admitted based on its service level agreement. Bandwidth manager 101 additionally ensures that no new flow is admitted if its admission could result in violation of the service level agreements of existing data flows. Packet scheduler 103 allocates bandwidth for transmission of packets awaiting service in accordance with the bandwidth reservation determined by bandwidth manager 101. These packets are distributed among a plurality of data queues (not shown), each of which is associated with a particular service level. All packets in each queue are to be granted service that is commensurate with the corresponding service level agreement. Packet scheduler 103 uses a scheduling algorithm to establish an ordered list of packets that are pending service. In accordance with the ordered list of packets, packet handler 105 prepares the head of line packet for transmission whenever the next transmission opportunity becomes available.
Given a set of packets in a plurality of queues, a scheduler establishes an order for the packets to be transmitted. Such an order is typically based on static prioritization of the queues or dynamic assignment of priorities to packets at the heads of the queues. Whenever there is an opportunity to transmit a packet, the packet with the highest priority is granted that opportunity. Dynamic prioritization of packets is commonly derived from a set of queue weights, which reflect a desired bias in assigning priorities to packets at the heads of respective queues. These queue weights can be chosen to implement a predetermined fair bandwidth allocation policy that meets the QoS objective of active flows.
There exist many prior-art scheduling algorithms that are QoS based. Such schedulers are capable of providing service to a particular user with a guaranteed rate and bounded delay. Although such QoS-based schedulers are adequate for static channel conditions, most of them do not consider varying conditions of the network and its effect on QoS received by existing flows. Static resource allocation mechanisms can be rendered ineffective and unfair in environments where bandwidth demand fluctuates and resource availability may vary.
There exist scheduling algorithms that can adapt to variation in network conditions, such as offered loads and available bandwidth. Some of these prior systems dynamically distribute available bandwidth among packets in different queues by updating queue weights based on queue lengths. Such systems are inherently unfair for they favor users transmitting packets with excessive rates. Such systems are also ineffective in guaranteeing QoS since the QoS of every flow is subject to compromise in an event of decreased available bandwidth. Other prior systems that adapt to variation in network conditions exist for multi-channel communication networks. Such systems dynamically distribute transmission resources among different channels such that overall system throughput is maximized. Brute-force maximization of system throughput by favoring transmission in good channels is inherently unfair. Moreover, these systems are also ineffective in guaranteeing QoS since all users transmitting packets over poor channels are penalized.
An additional scheduling algorithm is described in U.S. Pat. No. 2002/0147022A1, METHOD FOR PACKET SCHEDULING AND RADIO RESOURCE ALLOCATION IN A WIRELESS COMMUNICATION SYSTEM. This system provides a method of scheduling packet transmission that takes into consideration radio resource allocation at a wireless access node serving a plurality of cells, wherein each cell includes a base station and a plurality of mobile stations. The method uses an estimated transmit power level and an average effective data rate of all base stations in the system to determine a tentative transmission schedule for each of the mobile stations, wherein the tentative transmission schedule is modified for transmission in each cell based on current radio conditions in the cell. The tentative transmission schedule is chosen to maximize the value of a predetermined utility function, which can be configured to implement a desirable trade-off between system throughput maximization and fairness. A goal of the modified transmission schedules in this prior-art system is to offer an advantage to mobile stations in cells with good channel conditions to maximize efficiency, while ensuring fair resource allocation among all mobile stations. In the prior-art system, mobile stations in different cells are dynamically assigned priorities in reverse order of their current effective data rates relative to their respective average effective data rates. Although this prior-art system is adaptive to variation in network conditions, it is ineffective in guaranteeing QoS when available network resources fall short of that needed to sustain current offered load.
In many emerging networks, such as those supporting mission critical applications, it is necessary to protect the QoS of mission critical flows against variation of network conditions. Since prior-art QoS-based scheduling algorithms are deficient when scheduling packets on such communication systems, a need exists for a method and apparatus for dynamic preemptive scheduling data within such communication systems, wherein the QoS of high priority flows is protected against variation in network conditions at the expense of the QoS of low priority flows.